

#include <iostream>
#include <vector>
using namespace std;

 struct TreeNode 
 {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution
{
    using Node = TreeNode;
public:
    TreeNode* lowestCommonAncestor1(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        // if (!root)
        //     return nullptr;

        Node* res = root;

        _lowestCommonAncestor1(root, p, q, res);

        return res;
    }

    int minCostClimbingStairs1(vector<int>& cost)
    {
        int res = 0;
        int n = cost.size();
        int prev = 0, pprev = 0;

        for (int i = 2; i <= n; ++i)
        {
            res = min(pprev + cost[i - 2], prev + cost[i - 1]);
            pprev = prev;
            prev = res;
        }

        return res;
    }

    int minCostClimbingStairs2(vector<int>& cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1);

        for (int i = 2; i <= n; ++i)
        {
            dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }

        return dp[n];

    }

    TreeNode* lowestCommonAncestor2(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        Node* res = nullptr;

        for (Node* cur = root; ;)
        {
            if (p->val > cur->val && q->val > cur->val)
                cur = cur->right;
            else if (p->val < cur->val && q->val < cur->val)
                cur = cur->left;
            else
            {
                res = cur;
                break;
            }
        }

        return res;
    }

private:
    void _lowestCommonAncestor1(Node* root, Node* p, Node* q, Node*& res)
    {
        if (!root)
        {
            return;
        }
        if (root->val == p->val)
        {
            res = p;
            return;
        }
        if (root->val == q->val)
        {
            res = q;
            return;
        }

        bool pInLeft = _findNode(root->left, p);
        bool pInRight = !pInLeft;
        bool qInLeft = _findNode(root->left, q);
        bool qInRight = !qInLeft;

        if (pInLeft && qInLeft)
            _lowestCommonAncestor1(root->left, p, q, res);
        if (pInRight && qInRight)
            _lowestCommonAncestor1(root->right, p, q, res);
        if ((pInLeft && qInRight) || (pInRight && qInLeft))
            res = root;
    }

    bool _findNode(Node* root, Node* cur)
    {
        if (!root)
            return false;

        if (root->val == cur->val)
            return true;

        return _findNode(root->left, cur) || _findNode(root->right, cur);
    }
};

int main()
{


	return 0;
}